Corelab Seminar
2012-2013
Thanasis Lianeas (NTUA)
Network Design for Bottleneck Routing Games
Abstract.
In routing games, the network performance at equilibrium can be significantly improved
if we remove some edges from the network. This counterintuitive fact, widely known as Braess's paradox,
gives rise to the (selfish) network design problem, where we seek to recognize routing games suffering from
the paradox, and to improve the equilibrium performance by edge removal.
In this talk, we will focus on the network design problem for non-atomic bottleneck routing games,
where the individual cost of each player is the bottleneck cost of her path, and the social cost is the
bottleneck cost of the network. We shall see that even for games with strictly increasing linear latencies,
it is NP-hard not only to recognize instances suffering from the paradox,but also to distinguish between instances
for which the Price of Anarchy (PoA) can decrease to 1 and instances for which the PoA is as large as (n^0,121) and
cannot improve by edge removal. Thus, the network design problem for such games is NP-hard to approximate within
a factor of O(n^0,121-å), for any constant å>0.